#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
namespace YX
{
    template<typename T>
    struct forward_list_node
    {
        forward_list_node<T>* _next;
        T _data;

        forward_list_node(const T& data)
            :_next(nullptr)
            ,_data(data)
        {

        }

    };

    template<class T,class Ref,class Ptr>
    struct forward_list_iterator
    {
            typedef forward_list_node<T> node;

            node* _node;

            forward_list_iterator(node* n)
                :_node(n)
            {

            }

            // 值拷贝无需自己写
            //forward_list_iterator(const forward_list_iterator<T,Ref,Ptr>& copy)
            //{
            //    _node=copy._node;
            //}

            //forward_list_iterator<T,Ref,Ptr>& operator=(const forward_list_iterator<T,Ref,Ptr>& copy)
            //{
            //    _node=copy._node;
            //}

            forward_list_iterator& operator++()
            {
                _node=_node->_next;

                return *this;
            }

            forward_list_iterator operator++(int)
            {
                forward_list_iterator<T,Ref,Ptr> tmp(*this);

                _node=_node->_next;

                return tmp;
            }

            Ref operator*()
            {
                return _node->_data;
            }

            Ptr operator->()
            {
                return &(operator*());
            }
            
            bool operator!=(const forward_list_iterator<T,Ref,Ptr>& it)
            {
               return _node!=it._node;
            }

            bool operator==(const forward_list_iterator<T,Ref,Ptr>& it)
            {
               return  _node==it._node;
            }
    };

    template<class T>
    class forward_list 
    {   
        struct Equal 
        {
            bool operator()(const T& x,const T& y)
            {
                return x==y;
            }
        };

        typedef forward_list_node<T> node;
        private:
            node* _head;
        public:

            // 迭代器
            typedef forward_list_iterator<T,const T&,const T*> iterator;

            forward_list()
                :_head(new node(T()))
            {

            }

            template<typename InputIterator>
            forward_list(InputIterator first,InputIterator last)
                :_head(new node(T()))
            {
                while(first!=last)
                {
                    push_front(*first);
                    first++;
                }

                reverse();
            }

            forward_list(const forward_list<T>& copy)
                :_head(new node(T()))
            {
                forward_list<T> tmp(copy.begin(),copy.end());

                std::swap(_head,tmp._head);
            }

            forward_list(initializer_list<T> il)
                :_head(new node(T()))
            {
                typename initializer_list<T>::iterator it=il.begin();
                while(it!=il.end())
                {
                    push_front(*it);

                    it++;
                }

                reverse();
            }

            forward_list<T>& operator=(forward_list<T> copy)
            {
                std::swap(_head,copy._head);

                return *this;
            }

            void clear()
            {
                while(_head->_next!=nullptr)
                {
                    erase_after(iterator(_head));
                }
            }

            ~forward_list()
            {
                clear();

                delete _head;
            }

            void push_front(const T& data)
            {
                node* newNode=new node(data);

                newNode->_next=_head->_next;

                _head->_next=newNode;
            }

            void pop_front()
            {
                node* del=_head->_next;

                _head->_next=del->_next;
                
                delete del;
            }

            bool empty()
            {
                return _head->_next==nullptr;
            }

            std::size_t size()
            {
                node* curr=_head->_next;

                std::size_t ret=0;

                while(curr!=nullptr)
                {
                    ret++;
                    curr=curr->_next;
                }

                return ret;
            }

            iterator before_begin() const
            {
                return iterator(_head);
            }

            iterator begin() const 
            {
                return iterator(_head->_next);
            }

            iterator end() const 
            {
                return iterator(nullptr);
            }

            T& front()
            {
                return _head->_next->_data;
            }

            const T& front() const
            {
                return _head->_next->_data;
            }

            void reverse()
            {
                node* prev=nullptr;
                node* curr=_head->_next;

                while(curr!=nullptr)
                {
                    node* next=curr->_next;

                    curr->_next=prev;

                    prev=curr;

                    curr=next;

                }

                _head->_next=prev;

            }

            // 在position位置之后插入新结点---并返回新结点对应的迭代器
            iterator insert_after(iterator position,const T& data)
            {
                node* newNode=new node(data);

                newNode->_next=(position._node)->_next;

                (position._node)->_next=newNode;

                return iterator(newNode);
            }

            // 删除position位置之后的元素---并返回删除元素之后对应结点的迭代器
            iterator erase_after(iterator position)
            {
                node* del=(position._node)->_next;

                (position._node)->_next=del->_next;

                return iterator(del->_next);
            }

            //template <class InputIterator>  void assign (InputIterator first, InputIterator last);
            
            void splice_after(iterator position,forward_list<T>& l)
            {
                node* curr=(l._head)->_next;

                while(curr->_next!=nullptr)
                {
                    curr=curr->_next;
                }

                curr->_next=(position._node)->_next;

                (position._node)->_next=(l._head)->_next;

                l.clear();
            }

            template<typename Compare>
            void sort(Compare com)
            {
                vector<T> v;

                iterator it=begin();
                while(it!=end())
                {
                    v.push_back(*it);
                    it++;
                }

                std::sort(v.begin(),v.end(),com);

                clear();

                int i=v.size()-1;

                while(i>=0)
                {
                    push_front(v[i--]);
                }
            }

            // 按值删除---remove_if
            void remove(const T& val)
            {
                node* prev=_head;
                node* curr=_head->_next;

                while(curr!=nullptr)
                {
                    if(Equal().operator()(curr->_data,val))
                    {
                        curr=erase_after(iterator(prev));
                    }
                    else 
                    {
                        prev=curr;
                        curr=curr->_next;
                    }
                }
            }
    };
};
